370. Range Addition
Medium

You are given an integer length and an array updates where updates[i] = [startIdxi, endIdxi, inci].

You have an array arr of length length with all zeros, and you have some operation to apply on arr. In the ith operation, you should increment all the elements arr[startIdxi], arr[startIdxi + 1], ..., arr[endIdxi] by inci.

Return arr after applying all the updates.

 

Example 1:

Input: length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]]
Output: [-2,0,3,5,3]

Example 2:

Input: length = 10, updates = [[2,4,6],[5,6,8],[1,9,-4]]
Output: [0,-4,2,2,2,4,4,-4,-4,-4]

 

Constraints:

  • 1 <= length <= 105
  • 0 <= updates.length <= 104
  • 0 <= startIdxi <= endIdxi < length
  • -1000 <= inci <= 1000
Accepted
34.4K
Submissions
53.8K
Seen this question in a real interview before?
Companies
Related Topics
Similar Questions
Show Hint 1
Thinking of using advanced data structures? You are thinking it too complicated.
Show Hint 2
For each update operation, do you really need to update all elements between i and j?
Show Hint 3
Update only the first and end element is sufficient.
Show Hint 4
The optimal time complexity is O(k + n) and uses O(1) extra space.

Average Rating: 4.60 (25 votes)

Premium

Solution


Approach 1: Naïve Approach

Algorithm

The algorithm is trivial. For each update query, we iterate over the required update range and update each element individually.

Each query of updates is a tuple of 3 integers: start,endstart, end (the start and end indexes for the update range) and valval (the amount by which each array element in this range must be incremented).

Complexity Analysis

  • Time complexity : O(nk)O(n \cdot k) (worst case) where kk is the number of update queries and nn is the length of the array. Each of the kk update operations take up O(n)O(n) time (worst case, when all updates are over the entire range).

  • Space complexity : O(1)O(1). No extra space required.


Approach 2: Range Caching

Intuition

  • There is only one read query on the entire range, and it occurs at the end of all update queries. Additionally, the order of processing update queries is irrelevant.

  • Cumulative sums or partial_sum operations apply the effects of past elements to the future elements in the sequence.

Algorithm

The algorithm makes use of the above intuition to simply store changes at the borders of the update ranges (instead of processing the entire range). Finally a single post processing operation is carried out over the entire output array.

The two steps that are required are as follows:

  1. For each update query (start,end,val)(start, end, val) on the array arrarr, we need to do only two operations:

    • Update startstart boundary of the range:

    arrstart=arrstart+val arr_{start} = arr_{start} + val

    • Update just beyond the endend boundary of the range:

    arrend+1=arrend+1val arr_{end+1} = arr_{end+1} - val

  2. Final Transformation. The cumulative sum of the entire array is taken (0 - based indexing)

    arri=arri+arri1i[1,n) arr_i = arr_i + arr_{i-1} \quad \forall \quad i \in [1, n)

Formal Explanation

For each update query (start,end,val)(start, end, val) on the array arrarr, the goal is to achieve the result:

arri=arri+vali[start,end] arr_i = arr_i + val \quad \forall \quad i \in [start, end]

Applying the final transformation, ensures two things:

  1. It carries over the +val+val increment over to every element arri    istart arr_i \; \forall \; i \ge start .
  2. It carries over the val-val increment (equivalently, a +val+val decrement) over to every element arrj    j>end arr_j \; \forall \; j \gt end .

The net result is that:

arri=arri+vali[start,end]arrj=arrj+valval=arrji(end,length) \begin{aligned} arr_i &= arr_i + val \quad && \forall \quad i \in [start, end] \\ arr_j &= arr_j + val - val = arr_j \quad && \forall \quad i \in (end, length) \end{aligned}

which meets our end goal. It is easy to see that the updates over a range did not carry over beyond it due to the compensating effect of the val-val increment over the +val+val increment.

It is good to note that this works for multiple update queries because the particular binary operations here (namely addition and subtraction):

  • are closed over the entire domain of Integers. (A counter example is division which is not closed over all Integers).

  • are complementary operations. (As a counter example multiplication and division are not always complimentary due to possible loss of precision when dividing Integers).

Complexity Analysis

  • Time complexity : O(n+k)O(n + k). Each of the kk update operations is done in constant O(1)O(1) time. The final cumulative sum transformation takes O(n)O(n) time always.

  • Space complexity : O(1)O(1). No extra space required.


Further Thoughts

An extension of this problem is to apply such updates on an array where all elements are not the same.

In this case, the second approach requires that the original configuration must be stored separately before applying the final transformation. This incurs an additional space complexity of O(n)O(n).

@StefanPochmann suggested another method (see comment section) which does not require extra space, but requires an extra linear pass over the entire array. The idea is to apply reverse partial_sum operation on the array (for example, array [2,3,10,5][2, 3, 10, 5] transforms to [2,1,7,5][2, 1, 7, -5]) as an initialization step and then proceed with the second method as usual.


Another general, more complex version of this problem comprises of multiple read and update queries over ranges. Such problems can be solved quite efficiently with Segment Trees by applying a popular trick called Lazy Propogation.

Analysis written by @babhishek21.

Report Article Issue

Comments: 10
StefanPochmann's avatar
Read More

An extension of this problem is to apply such updates on an array where all elements are not the same. In this case, the second approach requires that the original configuration must be stored separately before applying the final transformation. This incurs an additional space complexity of O(n).

Why? Can't you just apply "reverse partial_sum" to initialize? For example if given the array [2, 3, 10, 5], just change it to [2, 1, 7, -5] first.

18
Show 4 replies
Reply
Share
Report
m2chan's avatar
Read More

How does one come up with the intuition to be able to come up with this on the spot?

2
Reply
Share
Report
user760's avatar
Read More

The "net result" equation in Formal Explanation section doesn't display correctly

1
Reply
Share
Report
ajDeViL's avatar
Read More

So good. So neat. Hints are pretty useful. I am not saying because this I got the elegant solution.

0
Reply
Share
Report
its_dark's avatar
Read More

Hi,

Can you please provide more explanation on the reverse_partial_sum method?

0
Reply
Share
Report
venkata-sai-krishn's avatar
Read More

Yes, it works, and that is a brilliant thought! Thanks @StefanPochmann

0
Reply
Share
Report
YoghurtBoy's avatar
Read More

How do you do partial_sum in java? is there any lib func?

or just

        for (int i = 1; i < length; ++i) {
            res[i] += res[i - 1];
        }

0
Reply
Share
Report
severance's avatar
Read More

amazes me that people can come up with solutions like this!

0
Reply
Share
Report
zhangbinqq53's avatar
Read More

Nice idea!

0
Reply
Share
Report
kkzeng's avatar
Read More

Beautiful solution!

0
Reply
Share
Report

You don't have any submissions yet.

/23
Contribute
|||
Saved
Trie
#208 Implement Trie (Prefix Tree)
Medium
#211 Design Add and Search Words Data Structure
Medium
#212 Word Search II
Hard
#336 Palindrome Pairs
Hard
#421 Maximum XOR of Two Numbers in an Array
Medium
#425 Word Squares
Hard
#472 Concatenated Words
Hard
#642 Design Search Autocomplete System
Hard
#648 Replace Words
Medium
#676 Implement Magic Dictionary
Medium
#677 Map Sum Pairs
Medium
#692 Top K Frequent Words
Medium
#720 Longest Word in Dictionary
Easy
#745 Prefix and Suffix Search
Hard
#1023 Camelcase Matching
Medium
#1032 Stream of Characters
Hard
#1065 Index Pairs of a String
Easy
#1638 Count Substrings That Differ by One Character
Medium
#1698 Number of Distinct Substrings in a String
Medium
#1707 Maximum XOR With an Element From Array
Hard
#1803 Count Pairs With XOR in a Range
Hard
#1804 Implement Trie II (Prefix Tree)
Medium
#1858 Longest Word With All Prefixes
Medium